/***
 *
 * 快速排序工作原理：
 * 首先，从数组中选择一个元素，这个元素被称为基准值（pivot）。
 * 接下来，找出比基准值小的元素以及比基准值大的元素。这被称为分区（partitioning）。
 * 对这两个子数组进行快速排序
 *
 *
 */

function quicksSort(arr) {
  const len = arr.length;
  if (len < 2) {
    return arr;
  }
  let minIdx = 0;
  let pivot = arr[minIdx]; //基准值

  let partitionMax = []; // 大于基准值
  let partitionMin = []; //小于基准值

  let max = [];
  let min = [];

  for (let i = 1; i < len; i++) {
    const item = arr[i];
    if (pivot >= item) {
      partitionMin.push(item);
    }
    if (pivot < item) {
      partitionMax.push(item);
    }
  }

  max = quicksSort(partitionMax);
  min = quicksSort(partitionMin);

  return [...min, ...[pivot], ...max];
}

console.log(quicksSort([2, 6, -1, 0, 8, 7, 4, 5, 3]));

// 基准调整为中间值
function quicksSort2(arr) {
  const len = arr.length;
  if (len < 2) {
    return arr;
  }
  let minIdx = Math.floor(len / 2);
  let pivot = arr[minIdx]; //基准值

  let greater = []; // 大于基准值
  let less = []; //小于基准值
  let equal = [];

  let max = [];
  let min = [];

  for (let i = 0; i < len; i++) {
    const item = arr[i];
    if (pivot > item) {
      less.push(item);
    }
    if (pivot < item) {
      greater.push(item);
    }

    if (pivot === item) {
      equal.push(item);
    }
  }

  max = quicksSort2(greater);
  min = quicksSort2(less);

  return [...min, ...equal, ...max];
}

console.log(quicksSort2([2, 6, -1, 0, 8, 7, 8, 5, 3]));
